/**
 * 二分查找
 */

const arr1 = [73, 12, 58, 91, 34, 6, 87, 45, 29, 63,
    5, 77, 41, 19, 85, 52, 99, 8, 66, 23,
    71, 38, 14, 89, 3, 56, 95, 28, 61, 9,
    47, 81, 36, 2, 74, 50, 17, 92, 40, 67];


const arr = arr1.sort((a, b) => a - b);//将数据变成有序数据    
let findCount = 0; //记录查找的次数
getFindCount = () => { //获取查找的次数,并清空查找的次数
    let count = findCount;
    findCount = 0;
    return count;
}
function myBinarySearch(arr, target, left = 0, right = arr.length - 1) {//传入一个数组和一个目标值,头指针和尾指针
    if (left >= right) return -1; //如果头指针大于尾指针,说明数据中没有目标值,返回-1
    findCount++; //查找次数加1
    let mid = Math.floor((left + right) / 2); //中间指针,向下取整
    if (arr[mid] === target) return { mid, value: arr[mid] }; //如果中间指针的值等于目标值,返回中间指针和值
    if (arr[mid] > target) return myBinarySearch(arr, target, left, mid - 1); //如果中间指针的值大于目标值,递归调用,将尾指针设置为中间指针-1
    if (arr[mid] < target) return myBinarySearch(arr, target, mid + 1, right); //如果中间指针的值小于目标值,递归调用,将头指针设置为中间指针+1
}
console.log('==========查找存在的元素67============')
console.log(myBinarySearch(arr, 67));
console.log(`查找次数: ${getFindCount()}`);
console.log(myBinarySearch(arr, 28));
console.log(`查找次数: ${getFindCount()}`);
console.log('==========查找不存在的元素167============')
console.log(myBinarySearch(arr, 167));   
console.log(`查找次数: ${getFindCount()}`);